#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int main()
{
	int T;
	scanf("%d", &T);
	long long a[1000003];
	a[1] = 1;
	a[2] = 3;
	for (int i = 3; i < 1000001; i++)
	{
		a[i] = (2 * a[i - 2] + a[i - 1]) % 1000000007;
	}
	long long n;
	while (T--)
	{
		scanf("%lld", &n);
		printf("%lld\n", a[n]);
	}
	return 0;
}